{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "'''\n",
    "GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints\n",
    "(https://arxiv.org/pdf/2305.13245)\n",
    "\n",
    "The TLDR of GQA vs normal MHSA is that storing lots of keys and values for many heads \n",
    "takes up a lot of memory, so we just share keys and values across multiple heads, grouping\n",
    "the keys/vals for a layer by the queries (which we keep one set of per head)\n",
    "so the MHSA is now \"grouped\" and less expensive, especially for longer sequences\n",
    "when the memory required to store lots of keys and values (see KV cache) grows large. \n",
    "'''\n",
    "import torch \n",
    "import torch.nn as nn \n",
    "import torch.nn.functional as F\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "torch.Size([8, 512, 768])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Here's MHSA baseline we'll compare GQA to, to check its speedup as a function of seqlen \n",
    "# Note. torch.einsum is confusing notationally when you first see it, but is one of the most fundamental and widely\n",
    "# used operations, generalizing matrix multiplication greatly, and it becomes very fast and intuitive to do \n",
    "# many operations at once when you get used to it. I highly recommend reading the docs and playing around \n",
    "# with some examples to get the hang of it. \n",
    "class mhsa(nn.Module): \n",
    "    def __init__(self, D=512, head_dim=64, causal=True): \n",
    "        super().__init__()\n",
    "        self.D = D \n",
    "        self.head_dim = head_dim \n",
    "        assert self.D % self.head_dim == 0 \n",
    "        self.nheads = self.D // self.head_dim \n",
    "        self.causal = causal \n",
    "\n",
    "        self.wq = nn.Linear(D, D)\n",
    "        self.wk = nn.Linear(D, D)\n",
    "        self.wv = nn.Linear(D, D)\n",
    "        self.wo = nn.Linear(D, D)\n",
    "\n",
    "\n",
    "    def forward(self, x): # BSD -> BSD\n",
    "        B, S, D = x.shape\n",
    "        q, k, v = self.wq(x), self.wk(x), self.wv(x) # x is BSD wq is DD\n",
    "\n",
    "        q = q.reshape(B, self.nheads, S, self.head_dim)\n",
    "        k = k.reshape(B, self.nheads, S, self.head_dim)\n",
    "        v = v.reshape(B, self.nheads, S, self.head_dim) \n",
    "\n",
    "        normalize = torch.sqrt(torch.tensor(self.head_dim))\n",
    "        A = torch.einsum('bnij,bnkj->bnik', q, k) # [B, N, S, D] @ [B, N, S, D] -> [B, N, S, S]\n",
    "        A = nn.functional.softmax(A/normalize, dim=-1)\n",
    "\n",
    "        # check if causal mask \n",
    "        if self.causal: # add -inf in A[j>i], because we don't want to attend to future tokens to mimic inference time \n",
    "            mask = torch.triu(torch.ones_like(A), diagonal=1).bool()\n",
    "            A = A.masked_fill(mask, float('-inf'))\n",
    "\n",
    "        preout = torch.einsum('bnij,bnjd->bnid', A, v) # BNSS @ BNSD -> BNSD\n",
    "        preout = preout.reshape(B, S, -1) # this concats the head outputs under the hood \n",
    "        return self.wo(preout)\n",
    "\n",
    "B, S, D = 8, 512, 768\n",
    "attn = mhsa(D=D) \n",
    "x = torch.randn(B, S, D)\n",
    "attn(x).shape # BSD -> BSD \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np \n",
    "\n",
    "class GQA(torch.nn.Module): \n",
    "    def __init__(self, D=512, head_dim=64, causal=True, group_size=4): \n",
    "        super().__init__()\n",
    "        self.D = D \n",
    "        self.head_dim = head_dim \n",
    "        assert self.D % self.head_dim == 0 \n",
    "        self.num_query_heads = self.D // self.head_dim \n",
    "        self.group_size = group_size\n",
    "        # In GQA, keys and values use fewer heads: \n",
    "        # each group of query heads will share a common key/value, so:\n",
    "        self.num_kv_heads = self.num_query_heads // self.group_size \n",
    "        self.causal = causal\n",
    "\n",
    "        self.D_kv = self.num_kv_heads * self.head_dim\n",
    "\n",
    "        self.wq = torch.nn.Linear(D, D)\n",
    "        self.wk = torch.nn.Linear(D, self.D_kv)\n",
    "        self.wv = torch.nn.Linear(D, self.D_kv)\n",
    "        self.wo = torch.nn.Linear(D, D)\n",
    "\n",
    "\n",
    "    def forward(self, x):  # Input x: [B, S, D] -> Output: [B, S, D]\n",
    "        B, S, D = x.shape\n",
    "        q = self.wq(x)  # [B, S, D]\n",
    "        k = self.wk(x)  # [B, S, D_kv]\n",
    "        v = self.wv(x)  # [B, S, D_kv]\n",
    "\n",
    "        # Reshape queries to have all query heads.\n",
    "        q = q.reshape(B, self.num_query_heads, S, self.head_dim)\n",
    "        k = k.reshape(B, self.num_kv_heads, S, self.head_dim)\n",
    "        v = v.reshape(B, self.num_kv_heads, S, self.head_dim)\n",
    "\n",
    "        # reshape kv to match q by interleaving\n",
    "        k = torch.repeat_interleave(k, self.group_size, dim=1)\n",
    "        v = torch.repeat_interleave(v, self.group_size, dim=1)\n",
    "\n",
    "        # Compute scaled dot-product attention.\n",
    "        normalize = torch.sqrt(torch.tensor(self.head_dim, dtype=q.dtype, device=q.device))\n",
    "        logits = torch.einsum('bnij,bnkj->bnik', q, k) / normalize  # [B, num_query_heads, S, S]\n",
    "\n",
    "        # Apply causal mask if needed.\n",
    "        if self.causal:\n",
    "            mask = torch.triu(torch.ones_like(logits), diagonal=1).bool()\n",
    "            logits = logits.masked_fill(mask, float('-inf'))\n",
    "\n",
    "        A = torch.nn.functional.softmax(logits, dim=-1)\n",
    "        preout = torch.einsum('bnij,bnjd->bnid', A, v)  # [B, num_query_heads, S, head_dim]\n",
    "        preout = preout.reshape(B, S, -1)  # Concatenate heads: [B, S, D]\n",
    "        return self.wo(preout)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA1cAAAIjCAYAAADvBuGTAAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjEwLjAsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvlHJYcgAAAAlwSFlzAAAPYQAAD2EBqD+naQAAYJJJREFUeJzt3Xt8z/X///H7e2czm/M2zHnOpyJrzqKmpEZlTjkrObTycaycSokilRLl0GFSk5CkWCenCBMVQnMIm1M2Nobt+fvDz/vrbcPeevHeuF0vl/el9nw9X6/34/l+se3u+Xo9XzZjjBEAAAAA4D9xc3UBAAAAAHArIFwBAAAAgAUIVwAAAABgAcIVAAAAAFiAcAUAAAAAFiBcAQAAAIAFCFcAAAAAYAHCFQAAAABYgHAFAAAAABYgXAEAgFvWmDFjZLPZXF0GgNsE4QrAbSEhIUEDBgxQpUqV5OvrK19fX1WrVk39+/fXli1bst1n9erVatu2rQIDA+Xt7a2yZcuqb9++2r9//1Xfa+jQobLZbIqKiroRQ7luNptNNptNvXv3znb7888/b+9z9OhRe3v37t3l5+d31eMOGDDAoe3IkSOKjo5WlSpVlC9fPhUvXlz169fXsGHDdOrUqWyP8+6778pmsyksLMypcTVr1kw1atRwap8rWbNmjcaMGaMTJ05YcrzcICMjQ7Nnz1azZs1UuHBh+5/lHj16aMOGDa4uDwBuKTZjjHF1EQBwIy1ZskRRUVHy8PBQ586dVbt2bbm5uWn79u1asGCB9u7dq4SEBJUpU8a+z9tvv63o6GiVL19e3bt3V3BwsLZt26YPPvhANptN33zzje6+++4s72WMUenSpeXh4aGkpCQlJSWpQIECN3O4V2Sz2eTj4yMfHx8lJSXJy8vLYXv58uV16NAhnTlzRkeOHFHRokUlXQhX8+fPv2Iostls6t+/v6ZOnSpJOn78uO644w6lpKSoZ8+eqlKlio4dO6YtW7ZoyZIl2rJli8qWLZvlOA0bNtTBgwe1Z88e7dy5UxUrVszRuJo1a6ajR4/q999/d+LTyN7rr7+uIUOGKCEhIdsa85rTp0+rXbt2WrZsmZo0aaI2bdqocOHC2rNnjz7//HP99ddf2rdvn0qVKuXqUm+Y8+fP6/z58/Lx8XF1KQBuBwYAbmG7du0y+fPnN1WrVjUHDx7Msv3cuXPmzTffNPv27bO3rVq1yri5uZnGjRub1NTULMcLDAw0JUqUMP/++2+W433//fdGkvn++++Np6enmTNnjuVjul6STGRkpHFzczMLFy502LZ69WojyTzyyCNGkjly5Ih9W7du3Uz+/Pmvetz+/fvbv544caKRZFavXp2lb3Jysjl9+nSW9r///ttIMgsWLDDFihUzY8aMyfG4mjZtaqpXr57j/lfz2muvGUkmISHBkuO5Wv/+/Y0k88Ybb2TZdv78efPaa6+Z/fv33/zCboJTp065ugQAtyEuCwRwS5s4caJSU1M1e/ZsBQcHZ9nu4eGhp59+WiEhIfa2l156STabTR9++KF8fX0d+leoUEETJ07UwYMHNWPGjCzHi4mJUbVq1dS8eXO1bNlSMTExOaqzRo0aat68eZb2zMxMlSxZUo8++qi9bd68eapbt64KFCggf39/1axZU2+++WaO3qdkyZJq0qSJ5s6dm6XumjVrWnJ53e7du+Xu7p7tzJ6/v3+2MwgxMTEqVKiQWrdurUcffTTHn1tObdmyRd27d1f58uXl4+OjoKAg9ezZU8eOHbP3GTNmjIYMGSJJKleunP0SyT179tj7fPLJJ6pbt67y5cunwoULq0OHDlkuE714meKff/6p5s2by9fXVyVLltTEiROz1HXmzBmNGTNGlSpVko+Pj4KDg9WuXTvt3r1bxhiVLVtWDz/8cLb7BQQE6Mknn7zimP/55x9Nnz5d9957r5555pks293d3TV48GCHWav4+Hjdf//98vf3l5+fn1q0aKFffvnFYb85c+bIZrNp1apVevrpp1WsWDEVLFhQTz75pM6ePasTJ06oa9euKlSokAoVKqShQ4fKXHKRzJ49e2Sz2fT666/rjTfeUJkyZZQvXz41bdo0y+xjTs6b9H/3Vf3555/q1KmTChUqpEaNGjlsu9Ty5cvVqFEjFSxYUH5+fqpcubKee+45hz6HDx9Wr169FBgYKB8fH9WuXVsffvihQ59LxzJjxgxVqFBB3t7euuuuu/Trr79e8dwAuHV5uLoAALiRlixZoooVK+b4Pp60tDTFxcWpcePGKleuXLZ9oqKi9MQTT+irr77S0KFD7e3p6en64osv9L///U+S1LFjR/Xo0UOJiYkKCgq66vtGRUVpzJgxWfquWrVKBw8eVIcOHSRd+KWwY8eOatGihSZMmCBJ2rZtm1avXq3o6OgcjbFTp06Kjo7WqVOn5Ofnp/Pnzys2NlaDBg3SmTNnrrjfpfdhXU2ZMmWUkZGhjz/+WN26dcvRPjExMWrXrp28vLzUsWNHTZs2Tb/++qvuuuuuHO1/LcuXL9fff/+tHj16KCgoSH/88YdmzJihP/74Q7/88otsNpvatWunv/76S59++qneeOMN+2WRxYoVkyS9/PLLGjlypNq3b6/evXvryJEjevvtt9WkSRPFx8erYMGC9vf7999/1apVK7Vr107t27fX/PnzNWzYMNWsWVP333+/pAv3Qj344IOKi4tThw4dFB0drZMnT2r58uX6/fffVaFCBXXp0kUTJ07U8ePHVbhwYfvxv/rqK6WkpKhLly5XHPM333yj8+fP6/HHH8/RZ/THH3+ocePG8vf319ChQ+Xp6anp06erWbNm+umnn7L8HRo4cKCCgoI0duxY/fLLL5oxY4YKFiyoNWvWqHTp0nrllVe0dOlSvfbaa6pRo4a6du3qsP9HH32kkydPqn///jpz5ozefPNN3XPPPdq6dasCAwNzfN4u9dhjjyk0NFSvvPKKQ6C7fJwPPvigatWqpRdffFHe3t7atWuXVq9ebe9z+vRpNWvWTLt27dKAAQNUrlw5xcbGqnv37jpx4kSWv2tz587VyZMn9eSTT8pms2nixIlq166d/v77b3l6eubo8wdwi3DxzBkA3DDJycn2S+Eu9++//5ojR47YX2lpacYYYzZv3mwkmejo6Kseu1atWqZw4cIObfPnzzeSzM6dO40xxqSkpBgfH59sL8m63I4dO4wk8/bbbzu09+vXz/j5+dnri46ONv7+/ub8+fPXPObl9P8v3zt+/Ljx8vIyH3/8sTHGmK+//trYbDazZ88eM3r06GwvC5R01dellwUmJiaaYsWKGUmmSpUqpm/fvmbu3LnmxIkT2da1YcMGI8ksX77cGGNMZmamKVWq1DXPwUU5uSzw4ud3qU8//dRIMj///LO97UqXBe7Zs8e4u7ubl19+2aF969atxsPDw6G9adOmRpL56KOP7G3p6ekmKCjIPPLII/a2WbNmGUlm8uTJWWrLzMw0xvzfn4tp06Y5bH/ooYdM2bJl7f2y8+yzzxpJJj4+/op9LhUZGWm8vLzM7t277W0HDx40BQoUME2aNLG3zZ4920gyERERDu8fHh5ubDab6du3r73t/PnzplSpUqZp06b2toSEBCPJ5MuXz/zzzz/29nXr1hlJ5tlnn7W35fS8Xfxz27Fjxyz9L2676I033sjyZ/xyU6ZMMZLMJ598Ym87e/asCQ8PN35+fiYlJcVhLEWKFDHHjx+39120aJGRZL766qsrvgeAWxOXBQK4ZaWkpEhStivdNWvWTMWKFbO/3nnnHUnSyZMnJemai1AUKFDA3veimJgY1atXz74QQ4ECBdS6descXeJWqVIl1alTR5999pm9LSMjQ/Pnz1ebNm2UL18+SVLBggWVmpqq5cuXX/OYV1KoUCG1atVKn376qaQL/+reoEEDhwU9Lufj46Ply5dn+7pcYGCgfvvtN/Xt21f//vuv3nvvPXXq1EnFixfXSy+9lGVGISYmRoGBgfbLIi+utDhv3jxlZGRc9zgvdfHzky5cUnf06FH7ZYubNm265v4LFixQZmam2rdvr6NHj9pfQUFBCg0N1Q8//ODQ38/Pz2FWycvLS/Xr19fff/9tb/viiy9UtGhRDRw4MMv7XZyRqVSpksLCwhz+DB0/flzffPONOnfufNUlxi/++c/JgioZGRn67rvvFBkZqfLly9vbg4OD1alTJ61atcp+vIt69erl8P5hYWEyxqhXr172Nnd3d9WrV89h3BdFRkaqZMmS9q/r16+vsLAwLV261N7m7Hnr27fvNcd6cYZx0aJFyszMzLbP0qVLFRQUpI4dO9rbPD099fTTT+vUqVP66aefHPpHRUWpUKFC9q8bN24sSdmOG8CtjXAF4JZ18ZfK7Fa5mz59upYvX65PPvkk230uD06XO3nypIoXL27/+sSJE1q6dKmaNm2qXbt22V8NGzbUhg0b9Ndff12z3qioKK1evVoHDhyQJP344486fPiww5Lu/fr1U6VKlXT//ferVKlS6tmzp5YtW3bNY1+uU6dOWr58ufbt26eFCxeqU6dOV+3v7u6uli1bZvvKTnBwsKZNm6ZDhw5px44deuutt1SsWDGNGjVKM2fOtPfLyMjQvHnz1Lx5cyUkJNg/t7CwMCUlJSkuLs7psWXn+PHjio6OVmBgoPLly6dixYrZL/tMTk6+5v47d+6UMUahoaEOobxYsWLatm2bDh8+7NC/VKlSWYJPoUKF9O+//9q/3r17typXriwPj6tfod+1a1etXr1ae/fulSTFxsbq3Llz17zcz9/fX9K1/yxLF5bOT0tLU+XKlbNsq1q1qjIzM7PcW1a6dGmHrwMCAiTJ4f7Fi+2Xjvui0NDQLG2VKlVyuMfN2fN2pUt5LxUVFaWGDRuqd+/eCgwMVIcOHfT55587BK29e/cqNDRUbm6OvyZVrVrVvv1Sl38WF4NWduMGcGsjXAG4ZQUEBCg4ODjbJbrDwsLUsmVLNWzY0KE9NDRUHh4eV3z2lXTh3qodO3Y4/At/bGys0tPTNWnSJIWGhtpfgwYNkqQczV5FRUXJGKPY2FhJ0ueff66AgAC1atXK3qd48eLavHmzFi9erIceekg//PCD7r///hzf23TRQw89JG9vb3Xr1k3p6elq3769U/vnlM1mU6VKlTRw4ED9/PPPcnNzc/gsvv/+ex06dEjz5s1z+Nwu1mPVwhbt27fX+++/r759+2rBggX67rvv7KH0SrMXl8rMzJTNZtOyZcuynb2bPn26Q393d/dsj3P5rF1OdOjQQZ6envbP4pNPPlG9evWyDUKXqlKliiRp69atTr9nTlxpjNm1X8+4JefP26UzXVeSL18+/fzzz1qxYoUef/xxbdmyRVFRUbr33nuve6bUyvMNIG9jQQsAt7TWrVvrgw8+0Pr161W/fv1r9vf19VWLFi20YsUK7d27N9tL5T7//HOlp6frscces7fFxMSoRo0aGj16dJb+06dP19y5czV27Nirvne5cuVUv359ffbZZxowYIAWLFigyMhIeXt7O/Tz8vJSmzZt1KZNG2VmZqpfv36aPn26Ro4cmeNnQ+XLl0+RkZH65JNPdP/999sXb7iRypcvr0KFCunQoUP2tpiYGBUvXtx+WealFixYoC+//FLvvfdejn5pvpJ///1XcXFxGjt2rEaNGmVv37lzZ5a+V7rMrkKFCjLGqFy5cqpUqdJ113L5MdetW6dz585dddGDwoUL2y8v7dy5s1avXq0pU6Zc8/j333+/3N3d9cknn1xzlqtYsWLy9fXVjh07smzbvn273NzcssxI/VfZff5//fWX/flizpw3Z7m5ualFixZq0aKFJk+erFdeeUXPP/+8fvjhB7Vs2VJlypTRli1blJmZ6TB7tX37dkm66iW0AG5vzFwBuKUNHTpUvr6+6tmzp5KSkrJsz+5fll944QUZY9S9e3edPn3aYVtCQoKGDh2qkJAQ+y+s+/fv188//6z27dvr0UcfzfLq0aOHdu3apXXr1l2z3qioKP3yyy+aNWuWjh496nBJoKQsS1C7ubmpVq1aki7MqDlj8ODBGj16tEaOHOnUfteybt06paamZmlfv369jh07Zp9xOX36tBYsWKAHH3ww289twIABOnnypBYvXvyf6rk4q3D5uc4uoOTPn1/Shcs8L9WuXTu5u7tr7NixWY5jjMlyXnLikUce0dGjR+0PX778mJd6/PHH9eeff2rIkCFyd3e3rx55NSEhIerTp4++++47vf3221m2Z2ZmatKkSfrnn3/k7u6u++67T4sWLXK4LC8pKUlz585Vo0aN7JcZWmXhwoX2S2ClC38+1q1bZ19N0Znz5ozjx49naatTp46k//s79MADDygxMdHhHsjz58/r7bfflp+fn5o2bfqfagBw62LmCsAtLTQ0VHPnzlXHjh1VuXJlde7cWbVr15YxRgkJCZo7d67c3NwcnvXTqFEjvfHGG3rmmWdUq1Ytde/eXcHBwdq+fbvef/99ubm5aeHChfYb4+fOnStjjB566KFsa3jggQfk4eGhmJiYay4J3759ew0ePFiDBw9W4cKFs9zT1Lt3bx0/flz33HOPSpUqpb179+rtt99WnTp17PeD5FTt2rVVu3Ztp/bJiY8//lgxMTFq27at6tatKy8vL23btk2zZs2Sj4+P/XlCixcv1smTJ6/4ud19990qVqyYYmJisoTMyx05ckTjxo3L0l6uXDl17txZTZo00cSJE3Xu3DmVLFlS3333nRISErL0r1u3riTp+eeft1+O16ZNG1WoUEHjxo3TiBEjtGfPHkVGRqpAgQJKSEjQl19+qSeeeEKDBw926nPq2rWrPvroIw0aNEjr169X48aNlZqaqhUrVqhfv34Oz7dq3bq1ihQpotjYWN1///0O9/tdzaRJk7R79249/fTT9iBbqFAh7du3T7Gxsdq+fbs9qI0bN87+/Kd+/frJw8ND06dPV3p6erbP6PqvKlasqEaNGumpp55Senq6pkyZoiJFitgfb+Dv75/j8+aMF198UT///LNat26tMmXK6PDhw3r33XdVqlQp+7OxnnjiCU2fPl3du3fXxo0bVbZsWc2fP98+a5iTRUIA3KZu+vqEAOACu3btMk899ZSpWLGi8fHxMfny5bMvE7558+Zs91m5cqV5+OGHTdGiRY3NZjOSTPHixc2hQ4cc+tWsWdOULl36qu/frFkzU7x4cXPu3Llr1tqwYUMjyfTu3TvLtvnz55v77rvPFC9e3Hh5eZnSpUubJ598MktN2dFlS6Zn50pLsefPnz/Hx92yZYsZMmSIufPOO03hwoWNh4eHCQ4ONo899pjZtGmTvV+bNm2Mj4+PSU1NveKxu3fvbjw9Pc3Ro0ev2Ofi0ufZvVq0aGGMMeaff/4xbdu2NQULFjQBAQHmscceMwcPHjSSzOjRox2O99JLL5mSJUsaNze3LMuyf/HFF6ZRo0Ymf/78Jn/+/KZKlSqmf//+ZseOHQ71ZLc0fLdu3UyZMmUc2tLS0szzzz9vypUrZzw9PU1QUJB59NFHHZZDv6hfv35Gkpk7d+4VP4vsnD9/3nzwwQemcePGJiAgwHh6epoyZcqYHj16ZFmmfdOmTSYiIsL4+fkZX19f07x5c7NmzRqHPheXYv/1118d2rP7s3Nx3Jf++bm4fPlrr71mJk2aZEJCQoy3t7dp3Lix+e233xz2zel5u9J7X7rtori4OPPwww+bEiVKGC8vL1OiRAnTsWNH89dffznsl5SUZHr06GGKFi1qvLy8TM2aNc3s2bMd+lw6lstl92cLwK3PZgx3WwJATrz00ksaNWqUnn/++WxnSYAb6dlnn9XMmTOVmJgoX19fV5dz3fbs2aNy5crptddec3q2DwByOy4LBIAcGjlypA4ePKiXX35ZpUuX1hNPPOHqknCbOHPmjD755BM98sgjeTpYAcCtjnAFAE6YNm2apk2b5uoycJs4fPiwVqxYofnz5+vYsWOKjo52dUkAgKsgXAEAkEv9+eef6ty5s4oXL6633nrLvqodACB34p4rAAAAALAAz7kCAAAAAAsQrgAAAADAAtxzlY3MzEwdPHhQBQoUkM1mc3U5AAAAAFzEGKOTJ0+qRIkScnO7+twU4SobBw8eVEhIiKvLAAAAAJBL7N+/X6VKlbpqH8JVNgoUKCDpwgfo7+/v4moAAAAAuEpKSopCQkLsGeFqCFfZuHgpoL+/P+EKAAAAQI5uF2JBCwAAAACwAOEKAAAAACxAuAIAAAAAC3DP1XUyxuj8+fPKyMhwdSm3JHd3d3l4eLAUPgAAAPIMwtV1OHv2rA4dOqS0tDRXl3JL8/X1VXBwsLy8vFxdCgAAAHBNhCsnZWZmKiEhQe7u7ipRooS8vLyYXbGYMUZnz57VkSNHlJCQoNDQ0Gs+sA0AAABwNcKVk86ePavMzEyFhITI19fX1eXcsvLlyydPT0/t3btXZ8+elY+Pj6tLAgAAAK6K6YDrxEzKjcdnDAAAgLyE314BAAAAwAKEKwAAAACwAPdcWajs8K9v2nvtebX1TXsvAAAAANfGzNVtJjExUdHR0apYsaJ8fHwUGBiohg0batq0aQ5Ly69Zs0YPPPCAChUqJB8fH9WsWVOTJ0++4nO9nnzySbm7uys2NvZmDQUAAADIVQhXt5G///5bd9xxh7777ju98sorio+P19q1azV06FAtWbJEK1askCR9+eWXatq0qUqVKqUffvhB27dvV3R0tMaNG6cOHTrIGONw3LS0NM2bN09Dhw7VrFmzXDE0AAAAwOW4LPA20q9fP3l4eGjDhg3Knz+/vb18+fJ6+OGHZYxRamqq+vTpo4ceekgzZsyw9+ndu7cCAwP10EMP6fPPP1dUVJR9W2xsrKpVq6bhw4erRIkS2r9/v0JCQm7q2AAAAABXY+bqNnHs2DF999136t+/v0OwupTNZtN3332nY8eOafDgwVm2t2nTRpUqVdKnn37q0D5z5kx16dJFAQEBuv/++zVnzpwbMQQAAAAgVyNc3SZ27dolY4wqV67s0F60aFH5+fnJz89Pw4YN019//SVJqlq1arbHqVKlir2PJO3cuVO//PKLfSarS5cumj17dpZLBwEAAIBbHeHqNrd+/Xpt3rxZ1atXV3p6ur39auHIy8vL/v+zZs1SRESEihYtKkl64IEHlJycrO+///7GFQ0AAADkQoSr20TFihVls9m0Y8cOh/by5curYsWKypcvnyQpNDRUkrRt27Zsj7Nt2zZVqlRJkpSRkaEPP/xQX3/9tTw8POTh4SFfX18dP36chS0AAABw2yFc3SaKFCmie++9V1OnTlVqauoV+0VERKhw4cKaNGlSlm2LFy/Wzp071b17d0nS0qVLdfLkScXHx2vz5s3216effqoFCxboxIkTN2g0AAAAQO7DaoG3kXfffVcNGzZUvXr1NGbMGNWqVUtubm769ddftX37dtWtW1f58+fX9OnT1aFDBz3xxBMaMGCA/P39FRcXpyFDhqhPnz564IEHJF1YyKJ169aqXbu2w/tUq1ZNzz77rGJiYtS/f39XDBUAAADOGBPg6gqyGpPs6gqcRriy0J5XW7u6hKuqUKGC4uPj9corr2jEiBH6559/5O3trWrVqmnw4MHq16+fJOnRRx/VDz/8oJdfflmNGzdWSkqKJGnChAkaOnSoJCkpKUlff/215s6dm+V93Nzc1LZtW82cOZNwBQAAgNuGzbCsWxYpKSkKCAhQcnKy/P39HbadOXNGCQkJKleunHx8fFxU4c115swZPfzww9q/f79++uknFStW7Ka97+32WQMAALgEM1dXdLVscDnuucI1+fj4aNGiReratat+/vlnV5cDAAAA5EpcFogc8fHx0fDhw11dBgAAAJBrMXMFAAAAABYgXAEAAACABQhXAAAAAGABwhUAAAAAWIBwBQAAAAAWIFwBAAAAgAUIVwAAAABgAZ5zZaWb+WTrXPLEagAAAAAXMHN1G+nevbtsNpv69u2bZVv//v1ls9nUvXt3e9/IyMgs/X788UfZbDadOHHC3vb++++rdu3a8vPzU8GCBXXHHXdo/Pjx2dZQpUoVeXt7KzEx0YohAQAAALkG4eo2ExISonnz5un06dP2tjNnzmju3LkqXbq008ebNWuWnnnmGT399NPavHmzVq9eraFDh+rUqVNZ+q5atUqnT5/Wo48+qg8//PA/jQMAAADIbbgs8DZz5513avfu3VqwYIE6d+4sSVqwYIFKly6tcuXKOX28xYsXq3379urVq5e9rXr16tn2nTlzpjp16qSmTZsqOjpaw4YNu75BAAAAALkQM1e3oZ49e2r27Nn2r2fNmqUePXpc17GCgoL0yy+/aO/evVftd/LkScXGxqpLly669957lZycrJUrV17XewIAAAC5EeHqNtSlSxetWrVKe/fu1d69e7V69Wp16dIlS78lS5bIz8/P4XX//fc79Bk9erQKFiyosmXLqnLlyurevbs+//xzZWZmOvSbN2+eQkNDVb16dbm7u6tDhw6aOXPmDR0nAAAAcDMRrm5DxYoVU+vWrTVnzhzNnj1brVu3VtGiRbP0a968uTZv3uzw+uCDDxz6BAcHa+3atdq6dauio6N1/vx5devWTa1atXIIWLNmzXIIcF26dFFsbKxOnjx54wYKAAAA3ETcc3Wb6tmzpwYMGCBJeuedd7Ltkz9/flWsWNGh7Z9//sm2b40aNVSjRg3169dPffv2VePGjfXTTz+pefPm+vPPP/XLL79o/fr1DvdZZWRkaN68eerTp49FowIAAABch3B1m2rVqpXOnj0rm82miIgIS49drVo1SVJqaqqkCwtZNGnSJEuImz17tmbOnEm4AgAAwC2BcHWbcnd317Zt2+z/f72eeuoplShRQvfcc49KlSqlQ4cOady4cSpWrJjCw8N17tw5ffzxx3rxxRdVo0YNh3179+6tyZMn648//rjiCoMAAABAXkG4stKYZFdX4BR/f///fIyWLVtq1qxZmjZtmo4dO6aiRYsqPDxccXFxKlKkiL744gsdO3ZMbdu2zbJv1apVVbVqVc2cOVOTJ0/+z7UAAAAArmQzxhhXF5HbpKSkKCAgQMnJyVkCyJkzZ5SQkKBy5crJx8fHRRXeHvisAQAAbpIxAa6uIKtcMnFxtWxwOVYLBAAAAAALEK4AAAAAwAKEKwAAAACwAOEKAAAAACxAuLpOrANy4/EZAwAAIC8hXDnJ09NTkpSWlubiSm59Fz/ji585AAAAkJvxnCsnubu7q2DBgjp8+LAkydfXVzabzcVV3VqMMUpLS9Phw4dVsGDB//SQYwAAAOBmIVxdh6CgIEmyByzcGAULFrR/1gAAAEBuR7i6DjabTcHBwSpevLjOnTvn6nJuSZ6ensxYAQAAIE8hXP0H7u7uBAAAAAAAkljQAgAAAAAsQbgCAAAAAAsQrgAAAADAAoQrAAAAALAA4QoAAAAALEC4AgAAAAALEK4AAAAAwAKEKwAAAACwQK4IV++8847Kli0rHx8fhYWFaf369VftHxsbqypVqsjHx0c1a9bU0qVLr9i3b9++stlsmjJlisVVAwAAAMD/cXm4+uyzzzRo0CCNHj1amzZtUu3atRUREaHDhw9n23/NmjXq2LGjevXqpfj4eEVGRioyMlK///57lr5ffvmlfvnlF5UoUeJGDwMAAADAbc7l4Wry5Mnq06ePevTooWrVqum9996Tr6+vZs2alW3/N998U61atdKQIUNUtWpVvfTSS7rzzjs1depUh34HDhzQwIEDFRMTI09Pz5sxFAAAAAC3MZeGq7Nnz2rjxo1q2bKlvc3NzU0tW7bU2rVrs91n7dq1Dv0lKSIiwqF/ZmamHn/8cQ0ZMkTVq1e/Zh3p6elKSUlxeAEAAACAM1waro4ePaqMjAwFBgY6tAcGBioxMTHbfRITE6/Zf8KECfLw8NDTTz+dozrGjx+vgIAA+yskJMTJkQAAAAC43bn8skCrbdy4UW+++abmzJkjm82Wo31GjBih5ORk+2v//v03uEoAAAAAtxqXhquiRYvK3d1dSUlJDu1JSUkKCgrKdp+goKCr9l+5cqUOHz6s0qVLy8PDQx4eHtq7d6/+97//qWzZstke09vbW/7+/g4vAAAAAHCGS8OVl5eX6tatq7i4OHtbZmam4uLiFB4enu0+4eHhDv0lafny5fb+jz/+uLZs2aLNmzfbXyVKlNCQIUP07bff3rjBAAAAALitebi6gEGDBqlbt26qV6+e6tevrylTpig1NVU9evSQJHXt2lUlS5bU+PHjJUnR0dFq2rSpJk2apNatW2vevHnasGGDZsyYIUkqUqSIihQp4vAenp6eCgoKUuXKlW/u4AAAAADcNlwerqKionTkyBGNGjVKiYmJqlOnjpYtW2ZftGLfvn1yc/u/CbYGDRpo7ty5euGFF/Tcc88pNDRUCxcuVI0aNVw1BAAAAACQzRhjXF1EbpOSkqKAgAAlJydz/xUAAABufWMCXF1BVmOSXV2BJOeywS23WiAAAAAAuALhCgAAAAAsQLgCAAAAAAsQrgAAAADAAoQrAAAAALAA4QoAAAAALEC4AgAAAAALEK4AAAAAwAKEKwAAAACwAOEKAAAAACxAuAIAAAAACxCuAAAAAMAChCsAAAAAsADhCgAAAAAsQLgCAAAAAAsQrgAAAADAAoQrAAAAALAA4QoAAAAALEC4AgAAAAALEK4AAAAAwAKEKwAAAACwAOEKAAAAACxAuAIAAAAACxCuAAAAAMAChCsAAAAAsADhCgAAAAAsQLgCAAAAAAsQrgAAAADAAoQrAAAAALAA4QoAAAAALEC4AgAAAAALEK4AAAAAwAKEKwAAAACwAOEKAAAAACxAuAIAAAAACxCuAAAAAMAChCsAAAAAsADhCgAAAAAsQLgCAAAAAAsQrgAAAADAAoQrAAAAALAA4QoAAAAALEC4AgAAAAALEK4AAAAAwAKEKwAAAACwAOEKAAAAACxAuAIAAAAACxCuAAAAAMAChCsAAAAAsADhCgAAAAAsQLgCAAAAAAsQrgAAAADAAoQrAAAAALAA4QoAAAAALEC4AgAAAAALeLi6AAAAAOB2Unb4164uIYs9Pq6u4NbAzBUAAAAAWIBwBQAAAAAWIFwBAAAAgAUIVwAAAABgAcIVAAAAAFiAcAUAAAAAFiBcAQAAAIAFCFcAAAAAYAHCFQAAAABYgHAFAAAAABYgXAEAAACABQhXAAAAAGABwhUAAAAAWIBwBQAAAAAWIFwBAAAAgAUIVwAAAABgAcIVAAAAAFiAcAUAAAAAFiBcAQAAAIAFCFcAAAAAYAHCFQAAAABYgHAFAAAAABYgXAEAAACABQhXAAAAAGABwhUAAAAAWIBwBQAAAAAWIFwBAAAAgAUIVwAAAABgAcIVAAAAAFiAcAUAAAAAFiBcAQAAAIAFckW4euedd1S2bFn5+PgoLCxM69evv2r/2NhYValSRT4+PqpZs6aWLl3qsH3MmDGqUqWK8ufPr0KFCqlly5Zat27djRwCAAAAgNucy8PVZ599pkGDBmn06NHatGmTateurYiICB0+fDjb/mvWrFHHjh3Vq1cvxcfHKzIyUpGRkfr999/tfSpVqqSpU6dq69atWrVqlcqWLav77rtPR44cuVnDAgAAAHCbsRljjCsLCAsL01133aWpU6dKkjIzMxUSEqKBAwdq+PDhWfpHRUUpNTVVS5YssbfdfffdqlOnjt57771s3yMlJUUBAQFasWKFWrRocc2aLvZPTk6Wv7//dY4MAAAAyKrs8K9dXUIWe3w6ubqErMYku7oCSc5lA5fOXJ09e1YbN25Uy5Yt7W1ubm5q2bKl1q5dm+0+a9eudegvSREREVfsf/bsWc2YMUMBAQGqXbt2tn3S09OVkpLi8AIAAAAAZ7g0XB09elQZGRkKDAx0aA8MDFRiYmK2+yQmJuao/5IlS+Tn5ycfHx+98cYbWr58uYoWLZrtMcePH6+AgAD7KyQk5D+MCgAAAMDtyOX3XN0ozZs31+bNm7VmzRq1atVK7du3v+J9XCNGjFBycrL9tX///ptcLQAAAIC8zqXhqmjRonJ3d1dSUpJDe1JSkoKCgrLdJygoKEf98+fPr4oVK+ruu+/WzJkz5eHhoZkzZ2Z7TG9vb/n7+zu8AAAAAMAZLg1XXl5eqlu3ruLi4uxtmZmZiouLU3h4eLb7hIeHO/SXpOXLl1+x/6XHTU9P/+9FAwAAAEA2PJzdISEhQStXrtTevXuVlpamYsWK6Y477lB4eLh8fHycLmDQoEHq1q2b6tWrp/r162vKlClKTU1Vjx49JEldu3ZVyZIlNX78eElSdHS0mjZtqkmTJql169aaN2+eNmzYoBkzZkiSUlNT9fLLL+uhhx5ScHCwjh49qnfeeUcHDhzQY4895nR9AAAAAJATOQ5XMTExevPNN7VhwwYFBgaqRIkSypcvn44fP67du3fLx8dHnTt31rBhw1SmTJkcFxAVFaUjR45o1KhRSkxMVJ06dbRs2TL7ohX79u2Tm9v/TbA1aNBAc+fO1QsvvKDnnntOoaGhWrhwoWrUqCFJcnd31/bt2/Xhhx/q6NGjKlKkiO666y6tXLlS1atXz3FdAAAAAOCMHD3n6o477pCXl5e6deumNm3aZFlNLz09XWvXrtW8efP0xRdf6N13383Ts0Q85woAAAA3Cs+5yqE8+JyrHM1cvfrqq4qIiLjidm9vbzVr1kzNmjXTyy+/rD179jhVMAAAAADkdTkKV1cLVpcrUqSIihQpct0FAQAAAEBe5PRqgZs2bdLWrVvtXy9atEiRkZF67rnndPbsWUuLAwAAAIC8wulw9eSTT+qvv/6SJP3999/q0KGDfH19FRsbq6FDh1peIAAAAADkBU6Hq7/++kt16tSRJMXGxqpJkyaaO3eu5syZoy+++MLq+gAAAAAgT3A6XBljlJmZKUlasWKFHnjgAUlSSEiIjh49am11AAAAAJBHOB2u6tWrp3Hjxunjjz/WTz/9pNatW0u68HDhi8+mAgAAAIDbjdPhasqUKdq0aZMGDBig559/XhUrVpQkzZ8/Xw0aNLC8QAAAAADIC3K0FPulatWq5bBa4EWvvfaa3N3dLSkKAAAAAPIap8PVlfj4+Fh1KAAAAADIc3IUrgoVKiSbzZajAx4/fvw/FQQAAAAAeVGOwtWUKVPs/3/s2DGNGzdOERERCg8PlyStXbtW3377rUaOHHlDigQAAACA3M5mjDHO7PDII4+oefPmGjBggEP71KlTtWLFCi1cuNDK+lwiJSVFAQEBSk5Olr+/v6vLAQAAwC2k7PCvXV1CFnt8Orm6hKzGJLu6AknOZQOnVwv89ttv1apVqyztrVq10ooVK5w9HAAAAADcEpwOV0WKFNGiRYuytC9atEhFihSxpCgAAAAAyGucXi1w7Nix6t27t3788UeFhYVJktatW6dly5bp/ffft7xAAAAAAMgLnA5X3bt3V9WqVfXWW29pwYIFkqSqVatq1apV9rAFAAAAALeb63rOVVhYmGJiYqyuBQAAAADyrOsKV5mZmdq1a5cOHz6szMxMh21NmjSxpDAAAAAAyEucDle//PKLOnXqpL179+ryVdxtNpsyMjIsKw4AAAAA8gqnw1Xfvn1Vr149ff311woODpbNZrsRdQEAAABAnuJ0uNq5c6fmz5+vihUr3oh6AAAAACBPcvo5V2FhYdq1a9eNqAUAAAAA8iynZ64GDhyo//3vf0pMTFTNmjXl6enpsL1WrVqWFQcAAAAAeYXT4eqRRx6RJPXs2dPeZrPZZIxhQQsAAAAAty2nw1VCQsKNqAMAAAAA8jSnw1WZMmVuRB0AAAAAkKdd10OEd+/erSlTpmjbtm2SpGrVqik6OloVKlSwtDgAAAAAyCucXi3w22+/VbVq1bR+/XrVqlVLtWrV0rp161S9enUtX778RtQIAAAAALme0zNXw4cP17PPPqtXX301S/uwYcN07733WlYcAAAAAOQVTs9cbdu2Tb169crS3rNnT/3555+WFAUAAAAAeY3T4apYsWLavHlzlvbNmzerePHiVtQEAAAAAHmO05cF9unTR0888YT+/vtvNWjQQJK0evVqTZgwQYMGDbK8QAAAAADIC5wOVyNHjlSBAgU0adIkjRgxQpJUokQJjRkzRk8//bTlBQIAAABAXuB0uLLZbHr22Wf17LPP6uTJk5KkAgUKWF4YAAAAAOQlToerhIQEnT9/XqGhoQ6haufOnfL09FTZsmWtrA8AAAAA8gSnF7To3r271qxZk6V93bp16t69uxU1AQAAAECe43S4io+PV8OGDbO033333dmuIggAAAAAtwOnw5XNZrPfa3Wp5ORkZWRkWFIUAAAAAOQ1ToerJk2aaPz48Q5BKiMjQ+PHj1ejRo0sLQ4AAAAA8gqnF7SYMGGCmjRposqVK6tx48aSpJUrVyolJUXff/+95QUCAAAAQF7g9MxVtWrVtGXLFrVv316HDx/WyZMn1bVrV23fvl01atS4ETUCAAAAQK7n9MyVdOGhwa+88orVtQAAAABAnuX0zJV04TLALl26qEGDBjpw4IAk6eOPP9aqVassLQ4AAAAA8gqnw9UXX3yhiIgI5cuXT5s2bVJ6erqkC6sFMpsFAAAA4HbldLgaN26c3nvvPb3//vvy9PS0tzds2FCbNm2ytDgAAAAAyCucDlc7duxQkyZNsrQHBAToxIkTVtQEAAAAAHmO0+EqKChIu3btytK+atUqlS9f3pKiAAAAACCvcTpc9enTR9HR0Vq3bp1sNpsOHjyomJgYDR48WE899dSNqBEAAAAAcj2nl2IfPny4MjMz1aJFC6WlpalJkyby9vbW4MGDNXDgwBtRIwAAAADkek6HK5vNpueff15DhgzRrl27dOrUKVWrVk1+fn43oj4AAAAAyBOu6zlXkuTl5aVq1aqpSpUqWrFihbZt22ZlXQAAAACQpzgdrtq3b6+pU6dKkk6fPq277rpL7du3V61atfTFF19YXiAAAAAA5AVOh6uff/5ZjRs3liR9+eWXyszM1IkTJ/TWW29p3LhxlhcIAAAAAHmB0+EqOTlZhQsXliQtW7ZMjzzyiHx9fdW6dWvt3LnT8gIBAAAAIC9wOlyFhIRo7dq1Sk1N1bJly3TfffdJkv7991/5+PhYXiAAAAAA5AVOrxb4zDPPqHPnzvLz81OZMmXUrFkzSRcuF6xZs6bV9QEAAABAnuB0uOrXr5/CwsK0b98+3XvvvXJzuzD5Vb58ee65AgAAAHDbcjpcSVLdunVVt25dh7bWrVtbUhAAAAAA5EU5uufq1Vdf1enTp3N0wHXr1unrr7/+T0UBAAAAQF6To3D1559/qnTp0urXr5+++eYbHTlyxL7t/Pnz2rJli9599101aNBAUVFRKlCgwA0rGAAAAAByoxxdFvjRRx/pt99+09SpU9WpUyelpKTI3d1d3t7eSktLkyTdcccd6t27t7p3786qgQAAAABuOzm+56p27dp6//33NX36dG3ZskV79+7V6dOnVbRoUdWpU0dFixa9kXUCAAAAQK7m9IIWbm5uqlOnjurUqXMDygEAAACAvMnphwgDAAAAALIiXAEAAACABQhXAAAAAGABwhUAAAAAWMDpcDV79mz78usAAAAAgAucDlfDhw9XUFCQevXqpTVr1tyImgAAAAAgz3E6XB04cEAffvihjh49qmbNmqlKlSqaMGGCEhMTb0R9AAAAAJAnOB2uPDw81LZtWy1atEj79+9Xnz59FBMTo9KlS+uhhx7SokWLlJmZeSNqBQAAAIBc6z8taBEYGKhGjRopPDxcbm5u2rp1q7p166YKFSroxx9/tKhEAAAAAMj9ritcJSUl6fXXX1f16tXVrFkzpaSkaMmSJUpISNCBAwfUvn17devWzepaAQAAACDXcjpctWnTRiEhIZozZ4769OmjAwcO6NNPP1XLli0lSfnz59f//vc/7d+/3/JiAQAAACC38nB2h+LFi+unn35SeHj4FfsUK1ZMCQkJ/6kwAAAAAMhLnA5XM2fOvGYfm82mMmXKXFdBAAAAAJAXOX1Z4NNPP6233norS/vUqVP1zDPPWFETAAAAAOQ5ToerL774Qg0bNszS3qBBA82fP9+SogAAAAAgr3E6XB07dkwBAQFZ2v39/XX06FFLigIAAACAvMbpcFWxYkUtW7YsS/s333yj8uXLW1IUAAAAAOQ1Ti9oMWjQIA0YMEBHjhzRPffcI0mKi4vTpEmTNGXKFKvrAwAAAIA8welw1bNnT6Wnp+vll1/WSy+9JEkqW7aspk2bpq5du1peIAAAAADkBU6HK0l66qmn9NRTT+nIkSPKly+f/Pz8rK4LAAAAAPKU6wpXFxUrVsyqOgAAAAAgT3N6QYukpCQ9/vjjKlGihDw8POTu7u7wAgAAAIDbkdMzV927d9e+ffs0cuRIBQcHy2az3Yi6AAAAACBPcTpcrVq1SitXrlSdOnVuQDkAAAAAkDc5fVlgSEiIjDGWFvHOO++obNmy8vHxUVhYmNavX3/V/rGxsapSpYp8fHxUs2ZNLV261L7t3LlzGjZsmGrWrKn8+fOrRIkS6tq1qw4ePGhpzQAAAABwKafD1ZQpUzR8+HDt2bPHkgI+++wzDRo0SKNHj9amTZtUu3ZtRURE6PDhw9n2X7NmjTp27KhevXopPj5ekZGRioyM1O+//y5JSktL06ZNmzRy5Eht2rRJCxYs0I4dO/TQQw9ZUi8AAAAAZMdmnJyGKlSokNLS0nT+/Hn5+vrK09PTYfvx48edKiAsLEx33XWXpk6dKknKzMxUSEiIBg4cqOHDh2fpHxUVpdTUVC1ZssTedvfdd6tOnTp67733sn2PX3/9VfXr19fevXtVunTpa9aUkpKigIAAJScny9/f36nxAAAAAFdTdvjXri4hiz0+nVxdQlZjkl1dgSTnsoHT91xNmTLleuvK4uzZs9q4caNGjBhhb3Nzc1PLli21du3abPdZu3atBg0a5NAWERGhhQsXXvF9kpOTZbPZVLBgwWy3p6enKz093f51SkpKzgcBAAAAALqOcNWtWzfL3vzo0aPKyMhQYGCgQ3tgYKC2b9+e7T6JiYnZ9k9MTMy2/5kzZzRs2DB17Njxiklz/PjxGjt27HWMAAAAAAAucPqeK0navXu3XnjhBXXs2NF+b9Q333yjP/74w9Li/qtz586pffv2MsZo2rRpV+w3YsQIJScn21/79++/iVUCAAAAuBU4Ha5++ukn1axZU+vWrdOCBQt06tQpSdJvv/2m0aNHO3WsokWLyt3dXUlJSQ7tSUlJCgoKynafoKCgHPW/GKz27t2r5cuXX/X6SG9vb/n7+zu8AAAAAMAZToer4cOHa9y4cVq+fLm8vLzs7ffcc49++eUXp47l5eWlunXrKi4uzt6WmZmpuLg4hYeHZ7tPeHi4Q39JWr58uUP/i8Fq586dWrFihYoUKeJUXQAAAADgLKfvudq6davmzp2bpb148eI6evSo0wUMGjRI3bp1U7169VS/fn1NmTJFqamp6tGjhySpa9euKlmypMaPHy9Jio6OVtOmTTVp0iS1bt1a8+bN04YNGzRjxgxJF4LVo48+qk2bNmnJkiXKyMiw349VuHBhh0AIAAAAAFZxOlwVLFhQhw4dUrly5Rza4+PjVbJkSacLiIqK0pEjRzRq1CglJiaqTp06WrZsmX3Rin379snN7f8m2Bo0aKC5c+fqhRde0HPPPafQ0FAtXLhQNWrUkCQdOHBAixcvliTVqVPH4b1++OEHNWvWzOkaAQAAAOBanH7O1eDBg7Vu3TrFxsaqUqVK2rRpk5KSktS1a1d17drV6fuuciOecwUAAIAbhedc5VAefM6V0/dcvfLKK6pSpYpCQkJ06tQpVatWTU2aNFGDBg30wgsvXHfRAAAAAJCXOX1ZoJeXl95//32NGjVKW7du1alTp3THHXcoNDT0RtQHAAAAAHmC0zNXL774otLS0hQSEqIHHnhA7du3V2hoqE6fPq0XX3zxRtQIAAAAALme0+Fq7Nix9mdbXSotLU1jx461pCgAAAAAyGucDlfGGNlstiztv/32mwoXLmxJUQAAAACQ1+T4nqtChQrJZrPJZrOpUqVKDgErIyNDp06dUt++fW9IkQAAAACQ2+U4XE2ZMkXGGPXs2VNjx45VQECAfZuXl5fKli2r8PDwG1IkAAAAAOR2OQ5X3bp1kySVK1dODRo0kKen5w0rCgAAAADyGqeXYm/atKn9/8+cOaOzZ886bOehuwAAAABuR04vaJGWlqYBAwaoePHiyp8/vwoVKuTwAgAAAIDbkdPhasiQIfr+++81bdo0eXt764MPPtDYsWNVokQJffTRRzeiRgAAAADI9Zy+LPCrr77SRx99pGbNmqlHjx5q3LixKlasqDJlyigmJkadO3e+EXUCAAAAQK7m9MzV8ePHVb58eUkX7q86fvy4JKlRo0b6+eefra0OAAAAAPIIp8NV+fLllZCQIEmqUqWKPv/8c0kXZrQKFixoaXEAAAAAkFc4Ha569Oih3377TZI0fPhwvfPOO/Lx8dGzzz6rIUOGWF4gAAAAAOQFTt9z9eyzz9r/v2XLltq+fbs2btyoihUrqlatWpYWBwAAAAB5hdMzV5crU6aM2rVrp8KFC+uJJ56woiYAAAAAyHP+c7i66NixY5o5c6ZVhwMAAACAPMWycAUAAAAAtzPCFQAAAABYgHAFAAAAABbI8WqB7dq1u+r2EydO/NdaAAAAACDPynG4CggIuOb2rl27/ueCAAAAACAvynG4mj179o2sAwAAAADyNO65AgAAAAALEK4AAAAAwAKEKwAAAACwAOEKAAAAACxAuAIAAAAACxCuAAAAAMAChCsAAAAAsADhCgAAAAAsQLgCAAAAAAsQrgAAAADAAoQrAAAAALAA4QoAAAAALEC4AgAAAAALEK4AAAAAwAKEKwAAAACwAOEKAAAAACxAuAIAAAAACxCuAAAAAMAChCsAAAAAsADhCgAAAAAsQLgCAAAAAAsQrgAAAADAAoQrAAAAALAA4QoAAAAALEC4AgAAAAALEK4AAAAAwAKEKwAAAACwAOEKAAAAACxAuAIAAAAACxCuAAAAAMAChCsAAAAAsADhCgAAAAAsQLgCAAAAAAsQrgAAAADAAoQrAAAAALAA4QoAAAAALEC4AgAAAAALEK4AAAAAwAKEKwAAAACwAOEKAAAAACxAuAIAAAAACxCuAAAAAMAChCsAAAAAsADhCgAAAAAsQLgCAAAAAAsQrgAAAADAAoQrAAAAALAA4QoAAAAALODh6gIAAABwixsT4OoKshqT7OoKcAti5goAAAAALEC4AgAAAAALEK4AAAAAwAKEKwAAAACwAOEKAAAAACxAuAIAAAAACxCuAAAAAMAChCsAAAAAsADhCgAAAAAsQLgCAAAAAAsQrgAAAADAAoQrAAAAALAA4QoAAAAALEC4AgAAAAALuDxcvfPOOypbtqx8fHwUFham9evXX7V/bGysqlSpIh8fH9WsWVNLly512L5gwQLdd999KlKkiGw2mzZv3nwDqwcAAACAC1warj777DMNGjRIo0eP1qZNm1S7dm1FRETo8OHD2fZfs2aNOnbsqF69eik+Pl6RkZGKjIzU77//bu+TmpqqRo0aacKECTdrGAAAAAAgmzHGuOrNw8LCdNddd2nq1KmSpMzMTIWEhGjgwIEaPnx4lv5RUVFKTU3VkiVL7G1333236tSpo/fee8+h7549e1SuXDnFx8erTp06TtWVkpKigIAAJScny9/f3/mBAQAA4P+MCXB1BVmNSXbZW5cd/rXL3vtK9vh0cnUJWbnwHF3KmWzgspmrs2fPauPGjWrZsuX/FePmppYtW2rt2rXZ7rN27VqH/pIUERFxxf45lZ6erpSUFIcXAAAAADjDZeHq6NGjysjIUGBgoEN7YGCgEhMTs90nMTHRqf45NX78eAUEBNhfISEh/+l4AAAAAG4/Ll/QIjcYMWKEkpOT7a/9+/e7uiQAAAAAeYyHq964aNGicnd3V1JSkkN7UlKSgoKCst0nKCjIqf455e3tLW9v7/90DAAAAAC3N5fNXHl5ealu3bqKi4uzt2VmZiouLk7h4eHZ7hMeHu7QX5KWL19+xf4AAAAAcLO4bOZKkgYNGqRu3bqpXr16ql+/vqZMmaLU1FT16NFDktS1a1eVLFlS48ePlyRFR0eradOmmjRpklq3bq158+Zpw4YNmjFjhv2Yx48f1759+3Tw4EFJ0o4dOyRdmPX6rzNcAAAAAHAlLg1XUVFROnLkiEaNGqXExETVqVNHy5Ytsy9asW/fPrm5/d/kWoMGDTR37ly98MILeu655xQaGqqFCxeqRo0a9j6LFy+2hzNJ6tChgyRp9OjRGjNmzM0ZGAAAAIDbjkufc5Vb8ZwrAAAAC/GcKwc85yqHeM4VAAAAANyeCFcAAAAAYAHCFQAAAABYgHAFAAAAABZw6WqBAAAAsFbuXCzB1RUANwczVwAAAABgAcIVAAAAAFiAcAUAAAAAFiBcAQAAAIAFCFcAAAAAYAHCFQAAAABYgHAFAAAAABYgXAEAAACABQhXAAAAAGABwhUAAAAAWIBwBQAAAAAWIFwBAAAAgAUIVwAAAABgAcIVAAAAAFiAcAUAAAAAFiBcAQAAAIAFCFcAAAAAYAHCFQAAAABYgHAFAAAAABYgXAEAAACABQhXAAAAAGABwhUAAAAAWIBwBQAAAAAWIFwBAAAAgAUIVwAAAABgAcIVAAAAAFiAcAUAAAAAFiBcAQAAAIAFCFcAAAAAYAHCFQAAAABYgHAFAAAAABYgXAEAAACABQhXAAAAAGABwhUAAAAAWIBwBQAAAAAWIFwBAAAAgAUIVwAAAABgAcIVAAAAAFiAcAUAAAAAFiBcAQAAAIAFCFcAAAAAYAHCFQAAAABYgHAFAAAAABYgXAEAAACABQhXAAAAAGABwhUAAAAAWIBwBQAAAAAWIFwBAAAAgAUIVwAAAABgAcIVAAAAAFiAcAUAAAAAFiBcAQAAAIAFCFcAAAAAYAHCFQAAAABYgHAFAAAAABbwcHUBAAAA/8mYAFdX4GhMsqsrAOAizFwBAAAAgAUIVwAAAABgAcIVAAAAAFiAcAUAAAAAFmBBCwAAkGNlh3/t6hKy2OPj6goA4AJmrgAAAADAAoQrAAAAALAA4QoAAAAALEC4AgAAAAALEK4AAAAAwAKEKwAAAACwAOEKAAAAACxAuAIAAAAACxCuAAAAAMAChCsAAAAAsADhCgAAAAAsQLgCAAAAAAsQrgAAAADAAoQrAAAAALAA4QoAAAAALEC4AgAAAAALeLi6AAC4WcoO/9rVJTjY82prV5cAAAAsRLgCAOQauS0AS9Ien06uLsHRmGRXVwAAuAIuCwQAAAAACxCuAAAAAMACXBaYB+TKy2S4V8QB5wgAAACEK1yfMQGuriAr7kNwxDnK/ThHAADcUnLFZYHvvPOOypYtKx8fH4WFhWn9+vVX7R8bG6sqVarIx8dHNWvW1NKlSx22G2M0atQoBQcHK1++fGrZsqV27tx5I4cAAAAA4Dbn8nD12WefadCgQRo9erQ2bdqk2rVrKyIiQocPH862/5o1a9SxY0f16tVL8fHxioyMVGRkpH7//Xd7n4kTJ+qtt97Se++9p3Xr1il//vyKiIjQmTNnbtawAAAAANxmXB6uJk+erD59+qhHjx6qVq2a3nvvPfn6+mrWrFnZ9n/zzTfVqlUrDRkyRFWrVtVLL72kO++8U1OnTpV0YdZqypQpeuGFF/Twww+rVq1a+uijj3Tw4EEtXLjwJo4MAAAAwO3EpfdcnT17Vhs3btSIESPsbW5ubmrZsqXWrl2b7T5r167VoEGDHNoiIiLswSkhIUGJiYlq2bKlfXtAQIDCwsK0du1adejQIcsx09PTlZ6ebv86OfnCPQcpKSnXPTYrZaanubqELFJsxtUlZOXC88U5yiEX/53KbeeJc5RVbjtHUi48T5yjLDhHjjhHOcTvDQ44R1d2MRMYc+3PyKXh6ujRo8rIyFBgYKBDe2BgoLZv357tPomJidn2T0xMtG+/2HalPpcbP368xo4dm6U9JCQkZwO5DeXC2/ClV3NlVS6TKz8NzpGDXPlpcI6yyHWfCOcoi1z3iXCOssiVnwjnyUGu/DRy2Tk6efKkAgKuXhOrBUoaMWKEw2xYZmamjh8/riJFishms7mwstwpJSVFISEh2r9/v/z9/V1dDrLBOcr9OEd5A+cp9+Mc5X6co9yPc3R1xhidPHlSJUqUuGZfl4arokWLyt3dXUlJSQ7tSUlJCgoKynafoKCgq/a/+N+kpCQFBwc79KlTp062x/T29pa3t7dDW8GCBZ0Zym3J39+fv4C5HOco9+Mc5Q2cp9yPc5T7cY5yP87RlV1rxuoily5o4eXlpbp16youLs7elpmZqbi4OIWHh2e7T3h4uEN/SVq+fLm9f7ly5RQUFOTQJyUlRevWrbviMQEAAADgv3L5ZYGDBg1St27dVK9ePdWvX19TpkxRamqqevToIUnq2rWrSpYsqfHjx0uSoqOj1bRpU02aNEmtW7fWvHnztGHDBs2YMUOSZLPZ9Mwzz2jcuHEKDQ1VuXLlNHLkSJUoUUKRkZGuGiYAAACAW5zLw1VUVJSOHDmiUaNGKTExUXXq1NGyZcvsC1Ls27dPbm7/N8HWoEEDzZ07Vy+88IKee+45hYaGauHChapRo4a9z9ChQ5WamqonnnhCJ06cUKNGjbRs2TL5+Pjc9PHdiry9vTV69Ogsl1Ii9+Ac5X6co7yB85T7cY5yP85R7sc5so7N5GRNQQAAAADAVbn8IcIAAAAAcCsgXAEAAACABQhXAAAAAGABwhUAAAAAWIBwBUnSzz//rDZt2qhEiRKy2WxauHChfdu5c+c0bNgw1axZU/nz51eJEiXUtWtXHTx40OEYf/31lx5++GEVLVpU/v7+atSokX744YebPJJb1/jx43XXXXepQIECKl68uCIjI7Vjxw6HPs2aNZPNZnN49e3bN8ux5syZo1q1asnHx0fFixdX//79b9YwbmljxozJ8vlXqVLFvn3GjBlq1qyZ/P39ZbPZdOLECYf99+zZo169eqlcuXLKly+fKlSooNGjR+vs2bM3eSS3lqt9f5MkY4xGjRql4OBg5cuXTy1bttTOnTvt2509L7t27VKBAgV4GH0O5eR725kzZ9S/f38VKVJEfn5+euSRR5SUlJTt8Y4dO6ZSpUpl+3csJiZGtWvXlq+vr4KDg9WzZ08dO3bsRg3tlvXqq6/aH31zUU7OUVxcnBo0aKACBQooKChIw4YN0/nz5x36GGP0+uuvq1KlSvL29lbJkiX18ssv34xh5WkZGRkaOXKkw/epl156SZeuW7dgwQLdd999KlKkiGw2mzZv3pzlOLt371bbtm1VrFgx+fv7q3379g7nkZ9T10a4giQpNTVVtWvX1jvvvJNlW1pamjZt2qSRI0dq06ZNWrBggXbs2KGHHnrIod+DDz6o8+fP6/vvv9fGjRtVu3ZtPfjgg0pMTLxZw7il/fTTT+rfv79++eUXLV++XOfOndN9992n1NRUh359+vTRoUOH7K+JEyc6bJ88ebKef/55DR8+XH/88YdWrFihiIiImzmUW1r16tUdPv9Vq1bZt6WlpalVq1Z67rnnst13+/btyszM1PTp0/XHH3/ojTfe0HvvvXfF/siZq31/k6SJEyfqrbfe0nvvvad169Ypf/78ioiI0JkzZyQ5d17OnTunjh07qnHjxjd0TLeSnHxve/bZZ/XVV18pNjZWP/30kw4ePKh27dple7xevXqpVq1aWdpXr16trl27qlevXvrjjz8UGxur9evXq0+fPjdsbLeiX3/9VdOnT8/yGV/rHP3222964IEH1KpVK8XHx+uzzz7T4sWLNXz4cIfjREdH64MPPtDrr7+u7du3a/Hixapfv/5NGVteNmHCBE2bNk1Tp07Vtm3bNGHCBE2cOFFvv/22vU9qaqoaNWqkCRMmZHuM1NRU3XfffbLZbPr++++1evVqnT17Vm3atFFmZqYkfk7liAEuI8l8+eWXV+2zfv16I8ns3bvXGGPMkSNHjCTz888/2/ukpKQYSWb58uU3stzb1uHDh40k89NPP9nbmjZtaqKjo6+4z/Hjx02+fPnMihUrbkKFt5/Ro0eb2rVrX7PfDz/8YCSZf//995p9J06caMqVK/ffi4MxJuv3t8zMTBMUFGRee+01e9uJEyeMt7e3+fTTT694nCudl6FDh5ouXbqY2bNnm4CAACtLv21c/r3txIkTxtPT08TGxtr7bNu2zUgya9euddj33XffNU2bNjVxcXFZ/o699tprpnz58g7933rrLVOyZMkbN5hbzMmTJ01oaKhZvny5w8+bnJyjESNGmHr16jkcb/HixcbHx8ekpKQYY4z5888/jYeHh9m+ffvNGdAtpHXr1qZnz54Obe3atTOdO3fO0jchIcFIMvHx8Q7t3377rXFzczPJycn2thMnThibzXbV3+X4OeWImStcl+TkZNlsNvtlL0WKFFHlypX10UcfKTU1VefPn9f06dNVvHhx1a1b17XF3qKSk5MlSYULF3Zoj4mJUdGiRVWjRg2NGDFCaWlp9m3Lly9XZmamDhw4oKpVq6pUqVJq37699u/ff1Nrv5Xt3LlTJUqUUPny5dW5c2ft27fvPx0vOTk5yzmGdRISEpSYmKiWLVva2wICAhQWFqa1a9decb/szsv333+v2NjYK86QIWcu/962ceNGnTt3zuEcValSRaVLl3Y4R3/++adefPFFffTRR3Jzy/rrTXh4uPbv36+lS5fKGKOkpCTNnz9fDzzwwA0e0a2jf//+at26tcO5kHJ2jtLT0+Xj4+OwX758+XTmzBlt3LhRkvTVV1+pfPnyWrJkicqVK6eyZcuqd+/eOn78+A0eWd7XoEEDxcXF6a+//pJ0YaZw1apVuv/++3N8jPT0dNlsNocHCfv4+MjNzc3hKozL8XPKEeEKTjtz5oyGDRumjh07yt/fX5Jks9m0YsUKxcfHq0CBAvLx8dHkyZO1bNkyFSpUyMUV33oyMzP1zDPPqGHDhqpRo4a9vVOnTvrkk0/0ww8/aMSIEfr444/VpUsX+/a///5bmZmZeuWVVzRlyhTNnz9fx48f17333sv10hYICwvTnDlztGzZMk2bNk0JCQlq3LixTp48eV3H27Vrl95++209+eSTFleKiy5ethwYGOjQHhgYeMVLmrM7L8eOHVP37t01Z84c+/dFOC+7722JiYny8vLKcg/bpecoPT1dHTt21GuvvabSpUtne+yGDRsqJiZGUVFR8vLyUlBQkAICAgjDOTRv3jxt2rRJ48ePz7ItJ+coIiJCa9as0aeffqqMjAwdOHBAL774oiTp0KFDki78jNq7d69iY2P10Ucfac6cOdq4caMeffTRGzu4W8Dw4cPVoUMHValSRZ6enrrjjjv0zDPPqHPnzjk+xt133638+fNr2LBhSktLU2pqqgYPHqyMjAz7ObocP6eyIlzBKefOnVP79u1ljNG0adPs7cYY9e/fX8WLF9fKlSu1fv16RUZGqk2bNlf8C4nr179/f/3++++aN2+eQ/sTTzyhiIgI1axZU507d9ZHH32kL7/8Urt375Z04ReXc+fO6a233lJERITuvvtuffrpp9q5cyeLj1jg/vvv12OPPaZatWopIiJCS5cu1YkTJ/T55587fawDBw6oVatWeuyxx7gnJBe50nnp06ePOnXqpCZNmriwurzvSt/brmXEiBGqWrWqwz8mXe7PP/9UdHS0Ro0apY0bN2rZsmXas2dPtov+wNH+/fsVHR2tmJiYLLNPOXXffffptddeU9++feXt7a1KlSrZZw0vzjRmZmYqPT1dH330kRo3bqxmzZpp5syZ+uGHH7IscgJHn3/+uWJiYjR37lxt2rRJH374oV5//XV9+OGHOT5GsWLFFBsbq6+++kp+fn4KCAjQiRMndOedd2Y7G8zPqStw8WWJyIV0hXuuzp49ayIjI02tWrXM0aNHHbatWLEiy3W6xhhTsWJFM378+BtZ7m2nf//+plSpUubvv/++Zt9Tp04ZSWbZsmXGGGNmzZplJJn9+/c79CtevLiZMWPGDan3dlevXj0zfPhwh7Zr3XN14MABExoaah5//HGTkZFxE6q8fVz+/W337t3Z3nvQpEkT8/TTTzu0Xe28BAQEGHd3d/vLzc3NSDLu7u5m5syZN2o4t5QrfW/L7v4pY4wpXbq0mTx5sjHGmNq1axs3N7dsP/9Ro0YZY4zp0qWLefTRRx2OsXLlSiPJHDx48MYN7Bbw5Zdf2j/Piy9JxmazGXd3d7NixYprnqOLMjMzzYEDB0xaWpr5888/jSSzfv16Y4wxo0aNMh4eHg7909LSjCTz3Xff3dAx5nWlSpUyU6dOdWh76aWXTOXKlbP0vdI9V5c6cuSI/XwGBgaaiRMnOmzn59SVedz8OIe86OKM1cUZjiJFijhsv3hfz+X/suHm5mZfYQb/jTFGAwcO1Jdffqkff/xR5cqVu+Y+F5dZDQ4OlnThshhJ2rFjh0qVKiVJOn78uI4ePaoyZcrcmMJvY6dOndLu3bv1+OOP53ifAwcOqHnz5qpbt65mz56d7b8WwjrlypVTUFCQ4uLiVKdOHUlSSkqK1q1bp6eeesre71rnZe3atcrIyLB/vWjRIk2YMEFr1qxRyZIlb8pY8qprfW+rW7euPD09FRcXp0ceeUTShe9h+/btU3h4uCTpiy++0OnTp+37/Prrr+rZs6dWrlypChUqSLrwc8rDw/HXHnd3d3sNuLIWLVpo69atDm09evRQlSpVNGzYMIWEhFzzHF1ks9lUokQJSdKnn36qkJAQ3XnnnZIu/Iw6f/68du/ebT9vF+8h4mfU1aWlpWX5vuTu7n7dv4MVLVpU0oV7SQ8fPuywQjQ/p67BxeEOucTJkydNfHy8iY+PN5LM5MmTTXx8vNm7d685e/aseeihh0ypUqXM5s2bzaFDh+yv9PR0Y8yFf+EoUqSIadeundm8ebPZsWOHGTx4sPH09DSbN2928ehuDU899ZQJCAgwP/74o8M5SEtLM8YYs2vXLvPiiy+aDRs2mISEBLNo0SJTvnx506RJE4fjPPzww6Z69epm9erVZuvWrebBBx801apVM2fPnnXFsG4p//vf/8yPP/5oEhISzOrVq03Lli1N0aJFzeHDh40xxhw6dMjEx8eb999/3766Znx8vDl27Jgxxph//vnHVKxY0bRo0cL8888/DucZ1+9q39+MMebVV181BQsWNIsWLTJbtmwxDz/8sClXrpw5ffq0Meb6zgurBebctb63GWNM3759TenSpc33339vNmzYYMLDw014ePgVj5nd7PDs2bONh4eHeffdd83u3bvNqlWrTL169Uz9+vVv5PBuWZevTpuTczRx4kSzZcsW8/vvv5sXX3zReHp6OswkZ2RkmDvvvNM0adLEbNq0yWzYsMGEhYWZe++99yaNKu/q1q2bKVmypFmyZIlJSEgwCxYsMEWLFjVDhw619zl27JiJj483X3/9tZFk5s2bZ+Lj4x2+l82aNcusXbvW7Nq1y3z88cemcOHCZtCgQfbt/Jy6NsIVjDH/94Po8le3bt3s08fZvX744Qf7MX799Vdz3333mcKFC5sCBQqYu+++2yxdutR1g7rFXOkczJ492xhjzL59+0yTJk1M4cKFjbe3t6lYsaIZMmRIlks1k5OTTc+ePU3BggVN4cKFTdu2bc2+fftcMKJbT1RUlAkODjZeXl6mZMmSJioqyuzatcu+ffTo0Vc9h7Nnz77iecb1u9r3N2MuXKY0cuRIExgYaLy9vU2LFi3Mjh077Ptfz3khXOXctb63GWPM6dOnTb9+/UyhQoWMr6+vadu27VV/mbvSpbdvvfWWqVatmsmXL58JDg42nTt3Nv/8888NGtmt7fJwlZNz1Lx5cxMQEGB8fHxMWFhYtr8jHDhwwLRr1874+fmZwMBA0717d/s/QOHKUlJSTHR0tCldurTx8fEx5cuXN88//7z9H8GNufL3stGjR9v7DBs2zAQGBhpPT08TGhpqJk2aZDIzM695DH5O/R+bMcyFAwAAAMB/xUWSAAAAAGABwhUAAAAAWIBwBQAAAAAWIFwBAAAAgAUIVwAAAABgAcIVAAAAAFiAcAUAAAAAFiBcAQAAAIAFCFcAANxGbDabFi5c6OoyAOCWRLgCADjlyJEjeuqpp1S6dGl5e3srKChIERERWr16tatLyzVyQ4AZM2aM6tSp49IaAOB24+HqAgAAecsjjzyis2fP6sMPP1T58uWVlJSkuLg4HTt2zNWlAQDgUsxcAQBy7MSJE1q5cqUmTJig5s2bq0yZMqpfv75GjBihhx56yKFf7969VaxYMfn7++uee+7Rb7/95nCsV199VYGBgSpQoIB69eql4cOHO8y0NGvWTM8884zDPpGRkerevbv96/T0dA0ePFglS5ZU/vz5FRYWph9//NG+fc6cOSpYsKC+/fZbVa1aVX5+fmrVqpUOHTrkcNxZs2apevXq8vb2VnBwsAYMGODUWJz1wQcfqGrVqvLx8VGVKlX07rvv2rft2bNHNptNCxYsUPPmzeXr66vatWtr7dq1Dsd4//33FRISIl9fX7Vt21aTJ09WwYIF7eMeO3asfvvtN9lsNtlsNs2ZM8e+79GjR9W2bVv5+voqNDRUixcv/k/jAQBcQLgCAOSYn5+f/Pz8tHDhQqWnp1+x32OPPabDhw/rm2++0caNG3XnnXeqRYsWOn78uCTp888/15gxY/TKK69ow4YNCg4OdggYOTVgwACtXbtW8+bN05YtW/TYY4+pVatW2rlzp71PWlqaXn/9dX388cf6+eeftW/fPg0ePNi+fdq0aerfv7+eeOIJbd26VYsXL1bFihVzPBZnxcTEaNSoUXr55Ze1bds2vfLKKxo5cqQ+/PBDh37PP/+8Bg8erM2bN6tSpUrq2LGjzp8/L0lavXq1+vbtq+joaG3evFn33nuvXn75Zfu+UVFR+t///qfq1avr0KFDOnTokKKiouzbx44dq/bt22vLli164IEH1Llz5+seDwDgEgYAACfMnz/fFCpUyPj4+JgGDRqYESNGmN9++82+feXKlcbf39+cOXPGYb8KFSqY6dOnG2OMCQ8PN/369XPYHhYWZmrXrm3/umnTpiY6Otqhz8MPP2y6detmjDFm7969xt3d3Rw4cMChT4sWLcyIESOMMcbMnj3bSDK7du2yb3/nnXdMYGCg/esSJUqY559/Ptux5mQs2ZFkvvzyy2y3VahQwcydO9eh7aWXXjLh4eHGGGMSEhKMJPPBBx/Yt//xxx9Gktm2bZsxxpioqCjTunVrh2N07tzZBAQE2L8ePXq0w+d5aW0vvPCC/etTp04ZSeabb7654ngAADnDzBUAwCmPPPKIDh48qMWLF6tVq1b68ccfdeedd9ovO/vtt9906tQpFSlSxD7T5efnp4SEBO3evVuStG3bNoWFhTkcNzw83Kk6tm7dqoyMDFWqVMnhfX766Sf7+0iSr6+vKlSoYP86ODhYhw8fliQdPnxYBw8eVIsWLbJ9j5yMxRmpqanavXu3evXq5XC8cePGZTlerVq1HGq+WK8k7dixQ/Xr13fof/nXV3PpsfPnzy9/f3/7sQEA148FLQAATvPx8dG9996re++9VyNHjlTv3r01evRode/eXadOnVJwcLDDvU8XXbwnKCfc3NxkjHFoO3funP3/T506JXd3d23cuFHu7u4O/fz8/Oz/7+np6bDNZrPZj5svX76r1mDVWC49nnThfqnLw+XlY7i0bpvNJknKzMx0+j2zk91nYtWxAeB2RrgCAPxn1apVsy89fueddyoxMVEeHh4qW7Zstv2rVq2qdevWqWvXrva2X375xaFPsWLFHBaeyMjI0O+//67mzZtLku644w5lZGTo8OHDaty48XXVXaBAAZUtW1ZxcXH2414qJ2NxRmBgoEqUKKG///5bnTt3vu7jVK5cWb/++qtD2+Vfe3l5KSMj47rfAwDgPMIVACDHjh07pscee0w9e/ZUrVq1VKBAAW3YsEETJ07Uww8/LElq2bKlwsPDFRkZqYkTJ6pSpUo6ePCgvv76a7Vt21b16tVTdHS0unfvrnr16qlhw4aKiYnRH3/8ofLly9vf65577tGgQYP09ddfq0KFCpo8ebJOnDhh316pUiV17txZXbt21aRJk3THHXfoyJEjiouLU61atdS6descjWnMmDHq27evihcvrvvvv18nT57U6tWrNXDgwByN5UoSEhK0efNmh7bQ0FCNHTtWTz/9tAICAtSqVSulp6drw4YN+vfffzVo0KAc1Txw4EA1adJEkydPVps2bfT999/rm2++sc9wSVLZsmXtNZQqVUoFChSQt7d3jo4PALhOrr7pCwCQd5w5c8YMHz7c3HnnnSYgIMD4+vqaypUrmxdeeMGkpaXZ+6WkpJiBAweaEiVKGE9PTxMSEmI6d+5s9u3bZ+/z8ssvm6JFixo/Pz/TrVs3M3ToUIcFGM6ePWueeuopU7hwYVO8eHEzfvx4hwUtLvYZNWqUKVu2rPH09DTBwcGmbdu2ZsuWLcaYCwtaXLrIgzHGfPnll+byH3/vvfeeqVy5sv0YAwcOdGosl5OU7WvlypXGGGNiYmJMnTp1jJeXlylUqJBp0qSJWbBggTHm/xa0iI+Ptx/v33//NZLMDz/8YG+bMWOGKVmypMmXL5+JjIw048aNM0FBQQ7n6pFHHjEFCxY0kszs2bPttV2+2EZAQIB9OwDg+tmMueyCdgAAXGDMmDFauHBhltke5EyfPn20fft2rVy50tWlAMBti8sCAQDIg15//XXde++9yp8/v7755ht9+OGH1/WsMACAdQhXAADkQevXr9fEiRN18uRJlS9fXm+99ZZ69+7t6rIA4LbGZYEAAAAAYAEeIgwAAAAAFiBcAQAAAIAFCFcAAAAAYAHCFQAAAABYgHAFAAAAABYgXAEAAACABQhXAAAAAGABwhUAAAAAWOD/AYl9jJX6LzRsAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 1000x600 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import time\n",
    "\n",
    "# profile relative latencies for different sequence lengths\n",
    "seq_lengths = [128, 256, 512, 1024, 2048, 4096, 8192]\n",
    "B, D = 1, 1024  # keep B, D fixed for now and vary S\n",
    "\n",
    "gqa_times = []\n",
    "mhsa_times = []\n",
    "\n",
    "for S in seq_lengths:\n",
    "    x = torch.randn(B, S, D, device='cuda')\n",
    "    \n",
    "    \n",
    "    attn_gqa = GQA(D=D).cuda()\n",
    "    \n",
    "    # warmup\n",
    "    for _ in range(5):\n",
    "        _ = attn_gqa(x)\n",
    "    \n",
    "    start = time.perf_counter()\n",
    "    for _ in range(10):\n",
    "        _ = attn_gqa(x)\n",
    "    torch.cuda.synchronize()\n",
    "    gqa_times.append((time.perf_counter() - start) / 10)\n",
    "\n",
    "    attn_mhsa = mhsa(D=D).cuda()\n",
    "    \n",
    "    # warmup\n",
    "    for _ in range(5):\n",
    "        _ = attn_mhsa(x)\n",
    "    \n",
    "    # profile MHSA\n",
    "    start = time.perf_counter()\n",
    "    for _ in range(10):\n",
    "        _ = attn_mhsa(x)\n",
    "    torch.cuda.synchronize()\n",
    "    mhsa_times.append((time.perf_counter() - start) / 10)\n",
    "\n",
    "# plot empirical speedup of GQA vs MHSA, as expected it does better for longer sequences\n",
    "# when storing lots of K/V for all the heads would be memory-expensive and thus \n",
    "# reduce the amount of memory we have available to speed up computation \n",
    "x = np.arange(len(seq_lengths))\n",
    "width = 0.35\n",
    "\n",
    "fig, ax = plt.subplots(figsize=(10, 6))\n",
    "ax.bar(x - width/2, gqa_times, width, label='GQA')\n",
    "ax.bar(x + width/2, mhsa_times, width, label='MHSA')\n",
    "\n",
    "ax.set_ylabel('Latency (seconds)')\n",
    "ax.set_xlabel('Sequence Length')\n",
    "ax.set_title('GQA vs MHSA Latency Comparison')\n",
    "ax.set_xticks(x)\n",
    "ax.set_xticklabels(seq_lengths)\n",
    "ax.legend()\n",
    "\n",
    "# one of the most satisfying plots in this codebase IMO!\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "envi",
   "language": "python",
   "name": "lingua_env"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
